#include <queue>
#include <sstream>
#include <utility>
#include "tree_node.h"

std::string bfs(const std::shared_ptr<Node> &root){
	std::queue<std::shared_ptr<Node> > q;
	q.push(root);
	std::stringstream sstr;
	while (!q.empty() ){
		std::shared_ptr<Node> curr = q.front();
		q.pop();
		if (curr) {
			sstr << curr->key << ' ';
			q.push(curr->left);
			q.push(curr->right);
		}
	}
	return sstr.str();
}

std::string level_order_2queue(const std::shared_ptr<Node> &root) {
	std::queue<std::shared_ptr<Node> > curr_queue, next_queue;
	curr_queue.push(root);
	std::stringstream sstr;
	while (!curr_queue.empty() ){
		std::shared_ptr<Node> curr = curr_queue.front();
		curr_queue.pop();
		if (curr) {
			sstr << curr->key << ' ';
			next_queue.push(curr->left);
			next_queue.push(curr->right);
		}
		else {
			sstr << "# ";
		}
		if (curr_queue.empty() ) {
			curr_queue.swap(next_queue);
			sstr << std::endl;
		}
	}
	return sstr.str();
}

std::string level_order_1queue(const std::shared_ptr<Node> &root) {
	std::queue<std::shared_ptr<Node> > curr_queue;
	curr_queue.push(root);
	int currlevel = 1;
	int nextlevel = 0;
	std::stringstream sstr;
	while (!curr_queue.empty() ){
		std::shared_ptr<Node> curr = curr_queue.front();
		curr_queue.pop();
		--currlevel;
		if (curr) {
			sstr << curr->key << ' ';
			curr_queue.push(curr->left);
			curr_queue.push(curr->right);
			nextlevel+=2;
		}
		else {
			sstr << "# ";
		}
		if (currlevel == 0 ) {
			currlevel = nextlevel;
			nextlevel = 0;
			sstr << std::endl;
		}
	}
	return sstr.str();
}

int height(const std::shared_ptr<Node>& node){
	if(!node)
		return -1;
	else
		return std::max(height(node->left), height(node->right) ) + 1; 
}

int bfs_height(const std::shared_ptr<Node> &root){
	std::queue<std::pair<std::shared_ptr<Node>, int> > q;
	q.push(std::make_pair(root,0) );
	int max_height = 0;
	while (!q.empty() ){
		auto curr = q.front();
		q.pop();
		if (curr.first) {
			max_height = std::max(max_height, curr.second);
			q.push(std::make_pair(curr.first->left, curr.second+1) );
			q.push(std::make_pair(curr.first->right, curr.second+1));
		}
	}
	return max_height;
}

